package leetcode_solution;

import java.util.HashMap;
import java.util.Map;

/**
 * 2661. 找出叠涂元素
 *
 * @author nagiumi
 * @date 2023/12/1
 */
public class Solution2661 {

    /*
    我的思路：遍历每一行每一列，找出每一行每一列最后涂上的一格，记录最小值。如果已经超过当前记录可以剪枝。
    官方思路：顺着正常的操作思路进行。
     */

    class Solution {
        public int firstCompleteIndex(int[] arr, int[][] mat) {
            int smallest = Integer.MAX_VALUE;
            int mMax = mat.length;
            int nMax = mat[0].length;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                map.put(arr[i], i);
            }

            for (int m = 0; m < mMax; m++) {
                int temp = 0;
                for (int n = 0; n < nMax; n++) {
                    if (map.get(mat[m][n]) > temp) {
                        temp = map.get(mat[m][n]);
                    }
                    if (temp >= smallest) {
                        break;
                    }
                }
                smallest = Math.min(temp, smallest);
            }

            for (int n = 0; n < nMax; n++) {
                int temp = 0;
                for (int m = 0; m < mMax; m++) {
                    if (map.get(mat[m][n]) > temp) {
                        temp = map.get(mat[m][n]);
                    }
                    if (temp >= smallest) {
                        break;
                    }
                }
                smallest = Math.min(temp, smallest);
            }

            return smallest;
        }
    }
}
